1. Field of the Invention
This invention relates to a method of routing in a communications network of interconnected nodes, and particularly, but not exclusively, to a method of routing in a sparsely connected network.
2. Related Art
A number of routing algorithms are known for routing in a network of interconnected nodes. For example, in the event of a fault preventing a message from being forwarded from a transit node to an adjacent node, the message is sent on an alternative route to that adjacent node via another transit node. In another example, known as source node routing, if there is a fault on a primary route to a destination node, the message is returned to the source node and a secondary route is tried from the source node to the destination node.
U.S. Pat. No. 5,649,108 (Spiegel et al.), issued 15 Jul. 1997, discloses a routing algorithm in which a source node, having a routing table containing, for each destination node, first choice, second choice, etc. complete end-to-end routes, i.e. each such route being a list of those nodes that a connection setup packet should pass through to establish a connection, selects one of first and second routing mode flags and selects from its routing table the first choice route to a destination node in response to a connection request. The source node generates a connection setup packet having a source route field, a record route field (for containing a list of those nodes through which the connection has already been established), a cumulative cost field, a cost threshold field, a crankback limit field, and a routing mode flag field. The source node copies the first choice end-to-end route from its routing table into the source route field, and establishes a connection to a first intermediate node located along the first choice route by sending the connection setup packet to that first intermediate node.
The first intermediate node is responsive to the first routing mode flag for extending the connection along the first choice route, i.e. testing the link to the next node of the first choice route as defined by the source route field and sending the packet to that next node if the link is available, and for updating the record route and cumulative cost fields.
If that link is not available, operation of the intermediate node is determined by which of the routing mode flags has been set. If the second routing mode flag has been set for that setup packet, i.e. requiring source node routing, then the first intermediate node sends a NACK to the source node. Upon receipt of the NACK, the source node releases that connection and generates a new setup packet, copying the stored end-to-end second choice route into the source route field of that new setup packet. However, if the second routing mode flag has been set for that setup packet, then that intermediate node records that link as being blocked for this connection, and attempts to find a new path tail from itself to the destination node by determining whether there is another path available in its routing table which has not been tested before. If there is, a path is selected and tested by adding the cost to the cumulative cost and comparing the new cumulative cost with the cost threshold. If the new cumulative cost is too high, control loops back to selecting from that routing table another path from among the possible paths to the destination node. If the new cumulative cost is not too high, the new path is checked to see whether it includes any links recorded as being blocked for this connection, and, if so, control loops back again to select another new path. If the new path does not include any blocked links, a check is made to see whether the new path causes any loops, and if so whether a crankback to the previous node would exceed the value in the crankback limit field. If the crankback limit would be exceeded, control loops back again to select another new path, but if not, then the crankback limit field is decremented from its initial value of one, and the setup packet cranked back to the previous node. On receipt of a cranked back setup packet, a node decrements the cumulative cost field in respect of the link from the cranking back node, removes that node's identifier from the record route field, and proceeds to find a new path tail from itself to the destination node.
In the event that an intermediate node fails to extend the connection along the first choice route, it will try to find a new path tail by repeatedly selecting and testing one of its respective set of first choice, second choice, etc. paths to the destination node until either a suitable path is found or all the paths have been tested.
Thus it can be seen that in Spiegel et al. the routing table in each node has to contain, for each respective destination node, a set of complete end-to end routes for copying into the source route fields of the setup packets. Conventionally, for such a routing algorithm there would be in the region of six to eight alternative routes for each destination node.
The article “Steady-State Performance of an Adaptive Sequential Routing Algorithm” by Harold M Heggestad, Proceedings of the National Telecommunications Conference (NTC '81), New Orleans, La., USA, 29 Nov. to 3 Dec. 1981, discloses a spill-forward routing algorithm and a sequential routing algorithm. In the spill-forward routing algorithm, each node has a routing table containing for each destination node a list of the links leaving that node ranked in order of their link blocking probabilities, and has a three-fold call attempt process, namely (1) a link leaving a source node is tried if and only if all links above it in the routing table are blocked, (2) when an intermediate node is reached, control is passed (“spills forward”) to it as if it had become the source node, and (3) when a call request is blocked at all exits from a node, it is dropped and re-initiated by the originator. In the sequential routing algorithm, which is a modification of the spill-forward routing algorithm, each node has a routing table similar to that for the spill-forward routing algorithm, and has a three-fold call attempt process, namely (1) a link leaving a source node is tried if and only if all links above it in the routing table are blocked, (2) a call request which is blocked at all exits from an intermediate node is cranked back to the closest preceding node having any still-untried links, and (3) a call request is ultimately blocked if and only if every possible source node/destination node route is blocked. When a node sends a call request packet to a neighbouring node, it extends a route history in the call request header by adding a field containing its own identity, the neighbouring node identity and an indication of whether the packet is being forwarded or returned.
Thus it can be seen that in Heggestad each node always acts in source mode and will only crankback a packet when all exits have been tried and found to be blocked.
In accordance with one aspect of the present invention, there is provided a method of routing a message in a communications network of interconnected nodes, the nodes being arranged to generate messages, each message having a destination information element containing the identity of a destination node for that message, a source information element containing the identity of the source node of that message, and a virtual source information element initially containing the identity of that source node, and each of the nodes having a respective routing table containing respective entries corresponding to source node/destination node pairs, each entry being in the form of a ranked pair of alternative next hop routes, the method comprising performing at a said node the steps of:                (a) comparing its own node identity with the destination node identity of a message to be routed; and, when it is not the destination node for that message,        (b) comparing its own node identity with the virtual source node identity of that message, and, if there is a match at step (b),                    (c) operating in source mode,                        else,                    (d) operating in transit mode;wherein step (c) comprises the substeps of                        (e) accessing its routing table in accordance with the virtual source node/destination node pair of that message to find the corresponding entry,        (f) forwarding the message to the higher ranking next hop route of that corresponding entry, and in the event that step (f) fails,        (g) forwarding the message to the lower ranking next hop route of that corresponding entry, and in the event that step (g) fails,        (h) replacing the content of the virtual source information element of the message with the node identity of the node from which that message was received, and        (i) sending that message back to that node from which it was received; and wherein step (d) comprises the substeps of        (j) forwarding the message to a preselected one of the ranked pair of alternative next hop routes of that corresponding entry, and in the event that step (j) fails,        (k) replacing the content of the virtual source information element of the message with its own node identity and performing step (c).        
The present invention is advantageous vis-a-vis Spiegel et al. in that a setup packet does not contain a source route field, thus reducing the packet overhead, and the node routing table does not contain sets of complete end-to-end routes, thus reducing the size of the routing table; and furthermore in that limiting each node to only a primary and a secondary route to a destination node enables an elegant binary pointer arrangement to be used for determining which of the routes is to be used for forwarding a packet depending upon whether the node recognises its own identity in the virtual source field of the packet.
The present invention is advantageous vis-a-vis Heggestad in that the network administration can establish a first choice route from a particular node to a destination node which has no node or link in common with a first choice route from another node to that destination node and for which that particular node is an intermediate node. By the use of the virtual source field of the present invention a node is able to determine whether it is to act in transit mode or in source mode and immediately know which outgoing link it has to test for blocking.
Preferably, for each said pair of alternative next hop routes, the two routes are node-disjoint routes.
Preferably substep (h) further comprises changing the state of a flag in a crankback information element of the message, and step (f) further comprises an initial substep (I) of checking whether the state of the crankback flag is indicative that the higher ranking route has already been attempted for that message.
In accordance with another aspect of the present invention, there is provided a node for use in a communications network of interconnected nodes, the node having a respective routing table containing respective entries corresponding to source node/destination node pairs, each entry being in the form of a ranked pair of alternative next hop routes, and being arranged:                to generate messages, each message having a destination information element containing the identity of a destination node for that message, a source information element containing the identity of the source node of that message, and a virtual source information element initially containing the identity of that source node, and each of the nodes;        to compare its own node identity with the destination node identity of a message to be routed; and, when it is not the destination node for that message;        to compare its own node identity with the virtual source node identity of that message;        to operate in source mode in the event of a match between its own node identity and the virtual source node identity by                    accessing its routing table in accordance with the virtual source node/destination node pair of that message to find the corresponding entry,            forwarding the message to the higher ranking next hop route of that corresponding entry, and in the event that that higher ranking next hop route is not available,            forwarding the message to the lower ranking next hop route of that corresporiding entry, and in the event that that lower ranking next hop route is not available,            replacing the content of the virtual source information element of the message with the node identity of the node from which that message was received, and            sending that message back to that node from which it was received;                        to operate in transit mode in the event of a mismatch between its own node identity and the virtual source node identity by                    accessing its routing table in accordance with the virtual source node/destination node pair of that message to find the corresponding entry,            forwarding the message to a preselected one of the ranked pair of alternative next hop routes of that corresponding entry, and in the event that that preselected one of the ranked pair of alternative next hop routes is unavailable,            replacing the content of the virtual source information element of the message with its own node identity and operating in source mode for that message.                        
In accordance with a further aspect of the present invention, there is provided a communications network of interconnected nodes, each of the nodes being as defined in the preceding paragraph.